package com.sen.Midium;

/**
 * Given a string s, find the longest palindromic substring in s.
 * You may assume that the maximum length of s is 1000.
 *
 * Example 1:
 *
 * Input: "babad"
 * Output: "bab"
 * Note: "aba" is also a valid answer.
 *
 *
 * Example 2:
 *
 * Input: "cbbd"
 * Output: "bb"
 *
 * Tag: String DP
 */
public class L005_Longest_Palindromic_Substring {
    /**
     * DP solution
     *
     * space complexity : O(n^2)
     * time complexity: O(n^2)
     * @param s
     * @return
     */
    public String longestPalindrome_dp(String s) {
        if(s == null || s.length() == 0) return s;
        String rst = "";
        int len = s.length();
        int max = 0;
        boolean[][] dp = new boolean[len][len];
        for(int j = 0; j < len; j++){
            for(int i = 0; i <= j; i++){
                dp[i][j] = s.charAt(i) == s.charAt(j) && ((j - i <= 2) || dp[i+1][j-1]);
                if(dp[i][j]){
                    if(j - 1 > max){
                        max = j - i + 1;
                        rst = s.substring(i, j + 1);
                    }
                }
            }
        }
        return rst;
    }


    /**
     * expand from the center
     * Time Complexity: O(n^2)
     * Space Complexity: O(1)
     */

    String rst = "";
    public String longestPalindrome_centerExpand(String s){

        int len =s.length();
        if(s == null || len == 0) return s;
        for(int i = 0; i < len; i++){
            util(s, i, i);
            util(s, i, i + 1);
        }

        return rst;
    }

    public void util(String s, int left, int right){
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        String current = s.substring(left + 1, right);
        if(current.length() > rst.length()){
            rst = current;
        }
    }

}
